Abraxus's Blog

dvCTF the more, the less Write Up

Details:

Points: 41

Jeopardy style CTF

Category: crypto

Write up:

Opening up the file I saw an e, n, and cipher text showing that this was obviously RSA. I then used alpertron to find the prime factors of n:

# prime factors
x = [2152978987,2178670709,2292487361,2367104263,2563604567,2571500203,2715012803,2788319507,2823467653,2903526499,2936894063,2989253341,3035960167,3068856233,3165948211,3391790461,3592739747,3613621433,3852924077,3876487189,3890394553,3898886171,3910833851,3961066927,3989645813,4014542803,4024893437,4029819973,4068148789,4109794417,4130412409,4226418397]

From here I wrote a python script to find phi(n), d, and then finally the answer:

# all prime factors
x = [2152978987,2178670709,2292487361,2367104263,2563604567,2571500203,2715012803,2788319507,2823467653,2903526499,2936894063,2989253341,3035960167,3068856233,3165948211,3391790461,3592739747,3613621433,3852924077,3876487189,3890394553,3898886171,3910833851,3961066927,3989645813,4014542803,4024893437,4029819973,4068148789,4109794417,4130412409,4226418397]

# n
n = 31599415905194296507531163994468257280886159280045654346389430217405819290199334738577568528414824952061262558727052291045816515870348057534996441596560396962516719727878569643953152119895297353348080193869479088114850667155373326828408666807238584625432868509009967976378084883283066242914464294233411627

# e
e = 65537

# cipher text
ct = 11371525982887248215036029303506383319725323173791816242922348267059091038845164126422411329763551336318264887183213679689757761368186436315189029720350805092964515239812759488055450797557376437081404871060787004042110689348646779529227539692241991396962852995556540999064671425810298104591755058349120054

# start value for phi(n)
i = 1

# loop through prime factors and multiply them together with (factor-1)*(nextFactor-1)...
for a in x:
	i = i * (a-1)

# inverse pow (3.8+ syntax, for previous versions of python use gmpy2.invert)
d = pow(e, -1, i)

# solve for the answer
ans = pow(ct, d, n)

# print the answer
print(bytes.fromhex(hex(ans)[2:]).decode('ascii'))

Once run the output was:

dvCTF{rs4_f4ctor1z4t10n!!!}